import java.util.Arrays;

public class Heap {
    private int[] elem;
    private int usedSize;

    public Heap(){
        this.elem = new int[10];
    }

    public Heap(int[] array){
        int n = array.length;
        this.elem = new int[n];
        for(int i = 0; i < array.length; i++){
            this.elem[i] = array[i];
            this.usedSize++;
        }
    }

    public void createHeap(){
        for(int parent = (this.usedSize - 1 - 1) / 2; parent >= 0; parent--){
            shiftDown(parent, this.usedSize);
        }
    }

    public void shiftDown(int parent, int usedSize){
        int child = parent * 2 + 1;
        while(child < usedSize){
            if(child + 1 < usedSize && this.elem[child] < this.elem[child + 1]){
                child++;
            }
            if(this.elem[parent] < this.elem[child]){
                swap(parent, child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }

    public void swap(int i, int j){
        int tmp = this.elem[i];
        this.elem[i] = this.elem[j];
        this.elem[j] = tmp;
    }

    public void offer(int val){
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,  2 * this.elem.length);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
        shiftUp(this.usedSize - 1);
    }

    private boolean isFull(){
        return this.usedSize == this.elem.length;
    }

    private void shiftUp(int child){
        while(child != 0){
            int parent = (child - 1) / 2;
            if(this.elem[child] > this.elem[parent]){
                swap(parent, child);
            }else{
                break;
            }
            child = parent;
        }
    }

    public int poll(){
        if(isEmpty()){
            return -1;
        }
        swap(0, this.usedSize - 1);
        this.usedSize--;
        shiftDown(0, this.usedSize);
        return this.elem[this.usedSize];
    }

    public boolean isEmpty(){
        return this.usedSize == 0;
    }

    public int size(){
        return this.usedSize;
    }
}
